//
//  Problem1395.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/17.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1395. 统计作战单位数
  n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。

 每 3 个士兵可以组成一个作战单位，分组规则如下：

 从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
 作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中  0 <= i < j < k < n
 请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

 示例 1：
     输入：rating = [2,5,3,4,1]
     输出：3
     解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
 示例 2：
     输入：rating = [2,1,3]
     输出：0
     解释：根据题目条件，我们无法组建作战单位。
 示例 3：
    输入：rating = [1,2,3,4]
    输出：4

 提示：
     n == rating.length
     3 <= n <= 1000
     1 <= rating[i] <= 10^5
     rating 中的元素都是唯一的
 */
@objcMembers class Problem1395: NSObject {
    func solution() {
        print(numTeams([2,5,3,4,1]))
        print(numTeams([2,1,3]))
        print(numTeams([1,2,3,4]))
    }
    
    /*
     中间节点：
     我们求出中间节点左侧: 左侧小于中间节点的个数：leftMinValue， 左侧大于中间节点的个数：leftMaxValue
     我们求出中间节点右侧: 右侧小于中间节点的个数：rightMinValue， 右侧大于中间节点的个数：rightMaxValue
     中间节点的个数就是：leftMinValue * rightMaxValue + leftMaxValue * rightMinValue
     */
    func numTeams(_ rating: [Int]) -> Int {
        var result: Int = 0
        var leftMinValue = 0
        var leftMaxValue = 0
        var rightMinValue = 0
        var rightMaxValue = 0
        for i in 1..<rating.count  {
            leftMinValue = 0
            leftMaxValue = 0
            rightMinValue = 0
            rightMaxValue = 0
            for j in 0..<i {
                if rating[j] > rating[i] {
                    leftMaxValue += 1
                } else if rating[j] < rating[i] {
                    leftMinValue += 1
                }
            }
            
            for j in i+1..<rating.count {
                if rating[j] > rating[i] {
                    rightMaxValue += 1
                } else if rating[j] < rating[i] {
                    rightMinValue += 1
                }
            }
            
            result += leftMinValue * rightMaxValue + leftMaxValue * rightMinValue
        }
        return result
    }
}
